home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / dev / c / vbcc.lha / vbcc / rd.c < prev    next >
C/C++ Source or Header  |  1997-12-30  |  19KB  |  479 lines
  1. /*  $VER: vbcc (rd.c) V0.4     */
  2. /*  verfuegbare Definitionen und constant propagation   */
  3.  
  4. #include "opt.h"
  5.  
  6. static char FILE_[]=__FILE__;
  7.  
  8. /*  fuer verfuegbare Definitionen   */
  9. unsigned int dcount;
  10. size_t dsize;
  11. struct IC **dlist;
  12. unsigned char **defs;       /*  gibt an, welche Definitionen, welche    */
  13.                             /*  Variablen definieren                    */
  14. /*  alle Definitionen, globaler oder Adr. fuer propagation etc.         */
  15. unsigned char *rd_globals,*rd_address,*rd_statics,*rd_drefs;
  16. /*  dasseble, aber hier nur die undefs  */
  17. unsigned char *rd_defs,*rd_tmp,*rd_parms;
  18.  
  19. /*  Bitvektor fuer geaenderte Variablen fuer ic_changes */
  20. unsigned char *rd_vars;
  21.  
  22. /*  rd_mode==0 => reaching definitions fuer constant-propagatione,      */
  23. /*  sonst fuer loop-invariant.                                          */
  24. int rd_mode;
  25.  
  26. int compare_const(union atyps *q1,union atyps *q2,int t)
  27. /*  vergleiht zwei Konstanten; -1, wenn q1<q2; 0, wenn q1==q1; 1 sonst  */
  28. {
  29.     zdouble d1,d2;zlong l1,l2;zulong u1,u2;zpointer p1,p2;
  30.     t&=NU;
  31.     eval_const(q1,t);p1=vpointer;d1=vdouble;l1=vlong;u1=vulong;
  32.     eval_const(q2,t);p2=vpointer;d2=vdouble;l2=vlong;u2=vulong;
  33.     if(t==POINTER) return(zpleq(p2,p1)?!zpeqto(p1,p2):-1);
  34.     if(t==DOUBLE||t==FLOAT) return(zdleq(d2,d1)?!zdeqto(d1,d2):-1);
  35.     if(t&UNSIGNED) return(zulleq(u2,u1)?!zuleqto(u1,u2):-1);
  36.     return(zlleq(l2,l1)?!zleqto(l1,l2):-1);
  37.     ierror(0);
  38. }
  39.  
  40. void print_rd(unsigned char *bitvector)
  41. /*  druckt Definitionen in einem Bitvektor */
  42. {
  43.     unsigned int i;
  44.     if(!bitvector) {printf("reaching definitions not available\n");return;}
  45.     for(i=1;i<=dcount;i++)
  46.         if(BTST(bitvector,i)) {printf("%3u:",i);pric2(stdout,dlist[i]);}
  47.     for(i=0;i<vcount-rcount;i++)
  48.         if(BTST(bitvector,i+dcount+1)) printf("%3u:\t\tundefined\t->%s\n",i+dcount+1,vilist[i]->identifier);
  49.     for(i=vcount-rcount;i<vcount;i++)
  50.         if(BTST(bitvector,i+dcount+1)) printf("%3u:\t\tundefined\t->(%s)\n",i+dcount+1,vilist[i]->identifier);
  51. }
  52.  
  53. void num_defs(void)
  54. /*  Numeriert alle Variablendefinitionen (nur elementare Typen noetig)  */
  55. /*  und erzeugt diverse Bitvektoren.                                    */
  56. {
  57.     int i=0;struct IC *p;
  58.     if(DEBUG&1024) printf("numerating definitions\n");
  59.     for(p=first_ic;p;p=p->next){
  60.         if(!(p->z.flags&VAR)&&p->code!=CALL){p->defindex=0;continue;}
  61. /*        if((p->z.v->vtyp->flags&NQ)>POINTER){p->defindex=0;continue;}*/
  62.         p->defindex=++i;
  63.     }
  64.     dcount=i;dsize=(dcount+CHAR_BIT+vcount)/CHAR_BIT;    /* +1, da bei 1 anfaengt */
  65.     if(DEBUG&1024) printf("%lu definitions, dsize=%lu\n",(unsigned long)dcount,(unsigned long)dsize);
  66.     /*  fuer jede Variable wird eine kuenstliche unbestimmte Def. erzeugt   */
  67.     /*  Feld erzeugen, dass zu jeder Variable alle Definitionen erhaelt    */
  68.     defs=mymalloc(sizeof(unsigned char *)*vcount);
  69.     for(i=0;i<vcount;i++){
  70.         defs[i]=mymalloc(dsize);
  71.         memset(defs[i],0,dsize);
  72.         BSET(defs[i],i+dcount+1);
  73.     }
  74.     dlist=mymalloc((dcount+1)*sizeof(struct IC *));
  75.     rd_globals=mymalloc(dsize);
  76.     memset(rd_globals,0,dsize);
  77.     rd_statics=mymalloc(dsize);
  78.     memset(rd_statics,0,dsize);
  79.     rd_address=mymalloc(dsize);
  80.     memset(rd_address,0,dsize);
  81.     rd_drefs=mymalloc(dsize);
  82.     memset(rd_drefs,0,dsize);
  83.  
  84.     rd_vars=mymalloc(vsize);
  85.  
  86.     for(p=first_ic;p;p=p->next){
  87.         if(p->defindex){
  88.             if(p->z.flags&VAR){
  89.                 i=p->z.v->index;
  90.                 if(p->z.flags&DREFOBJ) i+=vcount-rcount;
  91.                 BSET(defs[i],p->defindex);
  92.             }
  93.             dlist[p->defindex]=p;
  94.         }
  95.     }
  96.     if(DEBUG&2048){
  97.         for(i=1;i<=dcount;i++){ printf("Def%3d: ",i);pric2(stdout,dlist[i]);}
  98.         for(i=0;i<vcount;i++){
  99.             printf("Definitionen fuer <%s>:\n",vilist[i]->identifier);
  100.             print_rd(defs[i]);
  101.         }
  102.     }
  103.     for(i=0;i<vcount-rcount;i++){   /*  rd_globals berechnen    */
  104.         if(vilist[i]->vtyp->flags&CONST) continue;
  105.         if(vilist[i]->nesting==0||vilist[i]->storage_class==EXTERN) bvunite(rd_globals,defs[i],dsize);
  106.         if(vilist[i]->flags&USEDASADR) bvunite(rd_address,defs[i],dsize);
  107.         if(vilist[i]->storage_class==STATIC) bvunite(rd_statics,defs[i],dsize);
  108.         if(i<rcount){
  109.             bvunite(rd_address,defs[i+vcount-rcount],dsize);
  110.             bvunite(rd_globals,defs[i+vcount-rcount],dsize);
  111.             bvunite(rd_drefs,defs[i+vcount-rcount],dsize);
  112.         }
  113.     }
  114.     rd_parms=mymalloc(dsize);
  115.     memset(rd_parms,0,dsize);
  116.     for(i=0;i<vcount;i++){
  117.         struct Var *v=vilist[i];
  118.         if(i>=vcount-rcount||zl2l(v->offset)<0||(v->flags®PARM)||v->nesting==0||v->storage_class==EXTERN||v->storage_class==STATIC){
  119.             BSET(rd_parms,i+dcount+1);
  120.         }
  121.     }
  122. /*    if(DEBUG&1024){printf("rd_globals:\n");print_rd(rd_globals);}*/
  123. }
  124. int complete_def(struct IC *p)
  125. /*  Testet, ob eine Definition die Zielvariable komplett setzt oder nur */
  126. /*  teilweise.                                                          */
  127. {
  128.     struct Typ *t=p->z.v->vtyp;
  129.     zlong s1,s2;
  130.     if(p->z.flags&DREFOBJ) t=t->next;
  131.     if(!t) return(0);
  132.     s1=szof(t);
  133.     if(p->code==ASSIGN||p->code==GETRETURN) s2=p->q2.val.vlong;
  134.         else s2=sizetab[p->typf&NQ];
  135. /*    if(s1<s2) ierror(0);*/
  136.     if(zleqto(s1,s2)) return(1); else return(0);
  137. }
  138. void reaching_definitions(struct flowgraph *fg)
  139. /*  Berechnet die verfuegbaren Definitionen fuer jeden Block.   */
  140. {
  141.     struct flowgraph *g;struct IC *p;unsigned char *tmp;
  142.     int changed,pass,i,j;
  143.     /*  rd_gen und rd_kill fuer jeden Block berechnen   */
  144.     if(DEBUG&1024) printf("analysing reaching definitions\n");
  145.     tmp=mymalloc(dsize);
  146.     g=fg;
  147.     while(g){
  148.         g->rd_in=mymalloc(dsize);
  149.         memset(g->rd_in,0,dsize);
  150.         g->rd_out=mymalloc(dsize);
  151.         memset(g->rd_out,0,dsize);
  152.         g->rd_gen=mymalloc(dsize);
  153.         memset(g->rd_gen,0,dsize);
  154.         g->rd_kill=mymalloc(dsize);
  155.         memset(g->rd_kill,0,dsize);
  156.         p=g->end;
  157.         while(p){
  158.             if(p->defindex){
  159.                 int zi=-1;
  160.                 if(!BTST(g->rd_kill,p->defindex)) BSET(g->rd_gen,p->defindex);
  161.                 if(p->z.flags&VAR){
  162.                     if(!BTST(g->rd_kill,p->defindex)&&complete_def(p)){
  163.                         zi=p->z.v->index;
  164.                         if(p->z.flags&DREFOBJ) zi+=vcount-rcount;
  165.                         memcpy(tmp,defs[zi],dsize);
  166.                         bvdiff(tmp,g->rd_gen,dsize);
  167.                         bvunite(g->rd_kill,tmp,dsize);
  168.                     }
  169.                 }
  170.                 for(j=0;j<p->change_cnt;j++){
  171.                     i=p->change_list[j].v->index;
  172.                     if(p->change_list[j].flags&DREFOBJ) i+=vcount-rcount;
  173.                     if(i>=vcount) continue;
  174.                     if((i!=zi||(p->typf&NQ)>POINTER)&&!BTST(g->rd_kill,i+dcount+1)){
  175.                         BSET(g->rd_gen,i+dcount+1);
  176.                         if(i<rcount&&!BTST(g->rd_kill,dcount+1+i+vcount-rcount))
  177.                             BSET(g->rd_gen,i+vcount-rcount+dcount+1);
  178.                     }
  179.                 }
  180.             }
  181.  
  182.             if(p==g->start) break;
  183.             p=p->prev;
  184.         }
  185.         memcpy(g->rd_out,g->rd_gen,dsize);
  186.         g=g->normalout;
  187.     }
  188.  
  189.     /*  rd_in und rd_out fuer jeden Block berechnen */
  190.     /*  out(b)=gen(B) vorinitialisiert              */
  191.     if(DEBUG&1024) {printf("pass:");pass=0;}
  192.     do{
  193.         if(DEBUG&1024) {printf(" %d",++pass);fflush(stdout);}
  194.         changed=0;
  195.         g=fg;
  196.         while(g){
  197.             struct flowlist *lp;
  198.             /*  in(B)=U out(C) : C Vorgaenger von B */
  199.             if(g==fg) memcpy(g->rd_in,rd_parms,dsize);
  200.                 else  memset(g->rd_in,0,dsize);
  201.             lp=g->in;
  202.             while(lp){
  203.                 if(!lp->graph) ierror(0);
  204.                 if(lp->graph->branchout==g||!lp->graph->end||lp->graph->end->code!=BRA)
  205.                     bvunite(g->rd_in,lp->graph->rd_out,dsize);
  206.                 lp=lp->next;
  207.             }
  208.             /*  out(b)=gen(B) U (in(B)-kill(B)  */
  209.             memcpy(tmp,g->rd_in,dsize);
  210.             bvdiff(tmp,g->rd_kill,dsize);
  211.             bvunite(tmp,g->rd_gen,